﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Elderos.TextSearchers
{
	public class AhoCorasickSearcherNaive : TextSearcherBase
	{
		private Automaton _automaton = new Automaton();

		#region Overrides of TextSearcherBase

		private int _loadedStringsCount;

		public override int LoadedStringsCount
		{
			get { return _loadedStringsCount; }
		}

		protected override IEnumerable<Position> InnerSearch(string text)
		{
			var results = new List<Position>();

			//Начинаем с корня
			Node currentNode = _automaton.Root;
			for (int i = 0; i < text.Length; i++)
			{
				Node nextNode;
				do
				{
					//Пытаемся продвинуться по автомату
					nextNode = _automaton.Goto(currentNode, text[i]);

					//Если не получается, идем в Failure-узел
					if (nextNode == null)
						currentNode = _automaton.Fail(currentNode);
				} while (nextNode == null);

				currentNode = nextNode;

				IEnumerable<int> nodeResults =
					_automaton.GetNodeResults(currentNode);

				//Добавляем результаты текущего узла к общему списку
				if (nodeResults != null)
				{
					results.AddRange(
						nodeResults.Select(
							length => new Position(i - length + 1, length)));
				}
				//Продвигаемся на один символ вперед
			}

			return results;
		}

		protected override void ProcessString(string str)
		{
			_loadedStringsCount++;

			Node currentNode = _automaton.Root;
			for (int i = 0; i < str.Length; i++)
			{
				char currentChar = str[i];

				if (currentNode.Children == null)
					currentNode.Children = new Dictionary<char, Node>();

				if (currentNode.Children.ContainsKey(currentChar))
				{
					currentNode = currentNode.Children[currentChar];
					if (i == str.Length - 1)
					{
						if (currentNode.ResultLengths == null)
							currentNode.ResultLengths = new List<int>(1);
						currentNode.ResultLengths.Add(str.Length);
					}
					continue;
				}

				var nextNode = new Node();
				currentNode.Children.Add(currentChar, nextNode);
		if (i == str.Length - 1)
		{
			if (nextNode.ResultLengths == null)
				nextNode.ResultLengths = new List<int>(1);
			nextNode.ResultLengths.Add(str.Length);
		}

				currentNode = nextNode;
			}
		}

		protected override void OnStringsLoaded()
		{
			base.OnStringsLoaded();
			ProcessNodeFailures();
		}

		public void ProcessNodeFailures()
		{
			Node root = _automaton.Root;

			//С помощью очереди проходимся по всем узлам
			var queue = new Queue<Node>();

			if (root.Children == null)
				return;

			foreach (var node in root.Children.Values)
				queue.Enqueue(node);

			while (queue.Count > 0)
			{
				Node node = queue.Dequeue();

				if (node.Children == null)
					continue;

				foreach (KeyValuePair<char, Node> kv in node.Children)
				{
					//Узел
					Node child = kv.Value;
					//Символ перехода из одного узла в другой
					char ch = kv.Key;

					queue.Enqueue(child);
			
					//Идем к корню по "ошибочному" пути,
					//пока не наткнемся на возможность перехода
					//по символу, который привел нас в текущий узел
					Node failure = _automaton.Fail(child);
					while (_automaton.Goto(failure, ch) == null)
						failure = _automaton.Fail(failure);

					Node failureDestination = _automaton.Goto(failure, ch);

					child.FailureNode = failureDestination;

			if (failure.ResultLengths != null
				&& failure.ResultLengths.Count > 0)
			{
				child.ResultLengths = new List<int>(0);

				//Добавляем к результатам текущего узла
				//результаты Failure-узла
				child.ResultLengths.AddRange(failure.ResultLengths);
			}
				}
			}
		}

		#endregion

		private class Automaton
		{
			public Automaton()
			{
				_root.FailureNode = _root;
			}

			private Node _root = new Node();

			public Node Root
			{
				get { return _root; }
			}

			public Node Goto(Node fromNode, char ch)
			{
				if (fromNode.Children != null)
				{
					Node outNode;
					if (fromNode.Children.TryGetValue(ch, out outNode))
						return outNode;
				}
				if (fromNode == _root)
					return _root;
				return null;
			}

			public Node Fail(Node fromNode)
			{
				return fromNode.FailureNode ?? _root;
			}

			public IEnumerable<int> GetNodeResults(Node node)
			{
				return node.ResultLengths ?? new List<int>();
			}
		}

		/// <summary>
		/// Узел конечного автомата
		/// </summary>
		private class Node
		{
			public Node()
			{
			}

			/// <summary>
			/// Хеш-таблица переходов в дочерние состояния.
			/// Ключом является буква.
			/// </summary>
			public Dictionary<char, Node> Children { get; set; }

			/// <summary>
			/// Узел, куда мы перейдем при ошибке
			/// </summary>
			public Node FailureNode { get; set; }

			/// <summary>
			/// Длины результирующих строк, которые лежат в этом узле
			/// </summary>
			public List<int> ResultLengths { get; set; }

			public override string ToString()
			{
				return "Node: " + GetHashCode();
			}
		}
	}
}
